package com.jojo.intermediate.day7_string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 763、划分字母区间
 *
 * 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
 * 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
 * 返回一个表示每个字符串片段的长度的列表。
 *
 * 示例 1：
 * 输入：s = "ababcbacadefegdehijhklij"
 * 输出：[9,7,8]
 * 解释：
 * 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
 * 每个字母最多出现在一个片段中。
 * 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
 *
 * 示例 2：
 * 输入：s = "eccbbbbdec"
 * 输出：[10]
 */
public class DivideLetterInterval {

    /** myCode 双指针 */
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        //指向子串的开始索引
        int startIndex = 0;
        //指向子串的结束索引
        int endIndex = 0;
        for (int i = 0;i < s.length();i++){
            //从末尾寻找第一个和i处字符相同的位置作为endIndex
            for (int j = s.length() - 1;j > endIndex;j--){
                if (s.charAt(i) == s.charAt(j)){
                    endIndex = j;
                    break;
                }
            }
            //如果子串已遍历完则添加到list
            if (i == endIndex){
                list.add(endIndex - startIndex + 1);
                startIndex = endIndex = i + 1;
            }
        }
        return list;
    }

    /** pe.贪心算法 */
    public List<Integer> partitionLabels2(String s) {
        List<Integer> list = new ArrayList<>(26);
        Map<Character,Integer> map = new HashMap<>();
        int start = 0;
        int end = 0;
        //把每个字符最后一次出现的位置存起来
        for (int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            map.put(c,i);
        }
        for (int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            end = map.get(c) > end ? map.get(c) : end;
            if (i == end){
                list.add(end - start + 1);
                start = end = i + 1;
            }
        }
        return list;
    }

    public List<Integer> partitionLabels3(String s) {
        int[] last = new int[26];
        int length = s.length();
        for (int i = 0; i < length; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> partition = new ArrayList<Integer>();
        int start = 0, end = 0;
        for (int i = 0; i < length; i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                partition.add(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }

    public static void main(String[] args) {
        DivideLetterInterval divide = new DivideLetterInterval();
        List<Integer> list = divide.partitionLabels2("ababcbacadefegdehijhklij");
        System.out.println(list);
    }
}
